/*************************************************************
*
* CGM_WED_ALGO.CPP
*
* Winged-edge polygon mesh representation
* Various algorithms (searches, Dijkstra, etc.)
*************************************************************/
#include <m3d/m3d_stdafx.h>

#include <ap_comm.h>
#include <m3d.h>

#include <cgm.h>

class cgmQUERY* cgmWED_SYS::pQueryDefault;

/*************************************************************
* cgmWED_SYS::DepthFirstSearch ()
*    Depth First Search in graph (see Lypski p. 89)
* 
* IN  : winged-edge structure, nodes start search to
* RET : number of connectivity components
* NOTE: when search is in process callbacks for every
* edge and node are called. When edge callback return FALSE then this 
* edge is marked as ban edge. When node callback return FALSE then all
* edges of this node are marked as ban. When search stops the field compNmb of 
* cgmWED_NODE structure contains a zero based index of connectivity
* component or -1 if this node wasn't visited.
*************************************************************/
int cgmWED_SYS::DepthFirstSearch (cgmQUERY *pQuery)
{
   cgmWED_NODE  *pNode;
   int           curCompNmb, i;

   // clear processed flag from all nodes
   ClearStates();

   curCompNmb = 0;
   for (i = 0; i < nNode; i ++) {
      pNode = &nodeList[i];
      // skip processed nodes
      if (pNode->processedState == processedState) {
         continue;
      }
      pNode->processedState = processedState;
      if (!pQuery->ProcessNode(NULL, pNode)) {
         // stop search 
         continue;
      }
      DepthSearch(pNode, curCompNmb, pQuery);
      curCompNmb ++;
   }
   return curCompNmb;
}

/*************************************************************
* cgmWED_SYS::FaceDepthFirstSearch ()
*    Depth First Search in graph (see Lypski p. 89).
* 
* IN  : winged-edge structure, nodes start search to
* RET : number of connectivity components
* NOTE: as search progresses, virtual functions are called 
*       for every edge.
*************************************************************/
int cgmWED_SYS::FaceDepthFirstSearch (cgmQUERY *pQuery)
{
   // clear processed flag from all nodes
   ClearStates();

   int curCompNmb = 0;
   for (int i = 0; i < nFace; i ++) {
      cgmWED_FACE  *pFace = &faceList[i];
      // skip processed nodes
      if (pFace->processedState == processedState) {
         continue;
      }
      pFace->processedState = processedState;
      FaceDepthSearch(pFace, curCompNmb, pQuery);
      curCompNmb ++;
   }
   return curCompNmb;
}

/*************************************************************
* cgmWED_SYS::FaceBreadthFirstSearch()
*    Breadth First Search in graph (see Lypski p. 92).
* 
* IN  : winged-edge structure, nodes start search to
* NOTE: when search is in process callbacks for every
* edge and node are called. When edge callback return FALSE then this 
* edge is marked as ban edge. In case node callback return FALSE 
* the search is stopped and for every node pointer pNode->prevNode
* contain previous node in search or NULL if it's a source node.
*************************************************************/
void cgmWED_SYS::FaceBreadthFirstSearch (int nSourceFace, int *sourceFaceInd, cgmQUERY *pQuery)
{
   // clear processed flag from all Faces
   ClearStates();

   ASSERT(nSourceFace > 0 && nSourceFace <= nFace);
   // create initial front
   for (int i = 0; i < nSourceFace; i ++) {
      ASSERT(sourceFaceInd[i] >= 0 && sourceFaceInd[i] < nFace);
      faceQueue[i]           = &(faceList[sourceFaceInd[i]]);
      faceQueue[i]->prevFace = NULL;
      faceQueue[i]->dist     = 0.f;
      //faceQueue[i]->state.Set(CGM_WED_ST_PROCESSED|CGM_WED_ST_START);
      faceQueue[i]->processedState = processedState;
      
      // call user Face callback
      if (!pQuery->ProcessFace(NULL, faceQueue[i])) {
         // search is over
         return;
      }
   }
   int firstFace = 0;
   int lastFace  = nSourceFace;

   // while queue is not empty
   while (firstFace < lastFace ) {
      cgmWED_FACE * pFace = faceQueue[firstFace];
      // for all incident Faces
      for (int i = 0; i < pFace->nEdge; i ++) {
         cgmWED_EDGE * pEdge = pFace->edgeList[i];

         // choose incident Face
         cgmWED_FACE * pFaceNew = pFace->IncidentFace(pEdge);
         // skip faces
         if (pFaceNew == NULL) {
            continue;
         }
         // call user edge callback
         if (pEdge->processedState != processedState) {
            pEdge->processedState = processedState;
            if (!pQuery->ProcessEdge(pFace, pEdge)) {
               continue;
            }
         }
         // skip processed Faces
         if (pFaceNew->processedState == processedState) {
            continue;
         }
         // add Face to queue
         pFaceNew->processedState = processedState;
         pFaceNew->prevFace = pFace;
         pFaceNew->dist = pFace->dist + 1.f;

         ASSERT(lastFace >= 0 && lastFace < nFace);
         faceQueue[lastFace] = pFaceNew;
         lastFace++;
         // call user Face callback
         if (!pQuery->ProcessFace(pEdge, pFaceNew)) {
            // search is over
            return;
         }
      }
      firstFace ++;
   }
}

/*************************************************************
* cgmWED_SYS::Dijkstra ()
*    Finding a minimal distances from one points to all others
*  Dijkstra algo. (see Lypski p. 124)
* 
* IN  : nNode - number of nodes to calc dist to
*       nodeInd -  node indices 
*       nStartNode - number of start nodes
*       startNodeInd - indices of start nodes
*       startDist - distance to start nodes
* NOTE: when search is in process callbacks for every
* edge and node are called. When edge callback return FALSE then this 
* edge is marked as ban edge. In case node callback return FALSE 
* the search is stopped and for every node pointer pNode->prevNode
* contain previous node in search or NULL if it's a source node.
*************************************************************/
void cgmWED_SYS::Dijkstra (int nNodeSearch, int *nodeSearchInd, int nStartNode, int *startNodeInd, float *startDist, cgmQUERY *pQuery)
{
   cgmWED_NODE  *pNode = NULL, *pNodeAdd, *pNodeNext;
   cgmWED_EDGE  *pEdge;
   float         edgeLength, minDist;
   int           i;

   // clear processed flag from all nodes
   ClearStates();

   // store nodes to calc distances for
   if (nNodeSearch == 0 || nodeSearchInd == NULL) {
      // select all nodes by default
      nNodeSearch   = nNode;
      nodeSearchInd = NULL;
   }
   for (i = 0; i < nNodeSearch; i ++) {
      if (nodeSearchInd) {
         nodeQueue[i] = &nodeList[nodeSearchInd[i]];
      } else {
         nodeQueue[i] = &nodeList[i];
      }
      nodeQueue[i]->dist = M3D_INFINITY;
      nodeQueue[i]->searchState = searchState;
   }
   // create initial front
   for (i = 0; i < nStartNode; i ++) {
      pNode = &(nodeList[startNodeInd[i]]);
      pNode->prevNode = NULL;
      if (startDist) { 
         pNode->dist = startDist[i];
      } else {
         pNode->dist = 0.f;
      }
//      pNode->startState = startState;
      // initial nodes must be in search area
      ASSERT(pNode->searchState == searchState);
      // call user node callback
      if (!pQuery->ProcessNode(NULL, pNode)) {
         // search is over
         return;
      }
   }
   // while all nodes aren't processed
   while (TRUE) {
      // find nearest node to front
      minDist  = M3D_INFINITY;
      pNodeAdd = NULL;
      for (i = 0; i < nNode; i ++) {
         if (nodeQueue[i]->processedState == processedState) {
            // skip processed node 
            continue;
         }
         if (nodeQueue[i]->dist < minDist) {
            minDist  = nodeQueue[i]->dist;
            pNodeAdd = nodeQueue[i];
         }
      }
      if (pNodeAdd == NULL || minDist > 0.9f*M3D_INFINITY) {
         // stop search
         break;
      }
      // include node to front
      pNodeAdd->processedState = processedState;
      // call user node callback
      if (!pQuery->ProcessNode(NULL, pNodeAdd)) {
         // search is over
         return;
      }
      for (i = 0; i < pNodeAdd->nEdge; i ++) {
         pEdge = pNodeAdd->edgeList[i];
         // choose incident node
         pNodeNext = pNodeAdd->IncidentNode(pEdge);
         if (pNode->searchState != searchState) {
            // skip baned nodes
            continue;
         }
         if (pNodeNext->processedState == processedState) {
            // skip front nodes
            continue;
         }
         // call user edge callback
         if (!pQuery->ProcessEdge(pNodeAdd, pEdge)) {
            continue;
         }
         // calc edge length
         edgeLength = CalcDist(pEdge);
         // update distance from front 
         if (pNodeAdd->dist + edgeLength < pNodeNext->dist) {
            pNodeNext->dist     = pNodeAdd->dist + edgeLength;
            pNodeNext->prevNode = pNodeAdd;
         } 
      }
   }
   return;
}

/*************************************************************
* cgmWED_SYS::FaceDijkstra ()
*    Finding a minimal distances from one points to all others
*  Dijkstra algo. (See Lypski p. 124).
* 
* IN  : nNode - number of nodes to calc dist to
*       nodeInd -  face indices 
*       nStartNode - number of start faces
*       startNodeInd - indices of start faces
*       startDist - distance to start faces
* NOTE: when search is in process callbacks for every
* edge and face are called. When edge callback return FALSE then this 
* edge is marked as ban edge. In case face callback return FALSE 
* the search is stopped and for every face pointer pNode->prevNode
* contain previous face in search or NULL if it's a source face.
*************************************************************/
void cgmWED_SYS::FaceDijkstra (int nFaceSearch, int *faceSearchInd, int nStartFace, int *startFaceInd, float *startDist, cgmQUERY *pQuery)
{
   cgmWED_FACE  *pFace = NULL, *pFaceAdd, *pFaceNext;
   cgmWED_EDGE  *pEdge;
   float         edgeLength, minDist;

   // clear processed flag from all faces
   ClearStates();

   // store faces to calc distances for
   if (nFaceSearch == 0 || faceSearchInd == NULL) {
      // select all faces by default
      nFaceSearch   = nFace;
      faceSearchInd = NULL;
   }
   for (int i = 0; i < nFaceSearch; i ++) {
      if (faceSearchInd) {
         faceQueue[i] = &faceList[faceSearchInd[i]];
      } else {
         faceQueue[i] = &faceList[i];
      }
      faceQueue[i]->dist = M3D_INFINITY;
      faceQueue[i]->searchState = searchState;
   }

   // create initial front
   for (int i = 0; i < nStartFace; i ++) {
      pFace = &(faceList[startFaceInd[i]]);
      pFace->prevFace = NULL;
      if (startDist) { 
         pFace->dist = startDist[i];
      } else {
         pFace->dist = 0.f;
      }
      //pFace->state.Set(CGM_WED_ST_START);

      // initial faces must be in search area
      ASSERT(pFace->searchState == searchState);
      // call user face callback
      if (!pQuery->ProcessFace(NULL, pFace)) {
         // search is over
         return;
      }
   }
   // while all faces aren't processed
   while (TRUE) {
      // find nearest face to front
      minDist  = M3D_INFINITY;
      pFaceAdd = NULL;
      for (int i = 0; i < nFace; i ++) {
         if (faceQueue[i]->processedState == processedState) {
            // skip processed face 
            continue;
         }
         if (faceQueue[i]->dist < minDist) {
            minDist  = faceQueue[i]->dist;
            pFaceAdd = faceQueue[i];
         }
      }
      if (pFaceAdd == NULL || minDist > 0.9f*M3D_INFINITY) {
         // stop search
         break;
      }
      // include face to front
      pFaceAdd->processedState = processedState;
      // call user face callback
      if (!pQuery->ProcessFace(NULL, pFaceAdd)) {
         // search is over
         return;
      }
      for (int i = 0; i < pFaceAdd->nEdge; i ++) {
         pEdge = pFaceAdd->edgeList[i];
         // choose incident node
         pFaceNext = pFaceAdd->IncidentFace(pEdge);
         if (pFaceNext == NULL || pFace->searchState != searchState) {
            // skip banned nodes
            continue;
         }
         if (pFaceNext->processedState == processedState) {
            // skip front nodes
            continue;
         }
         // call user edge callback
         if (!pQuery->ProcessFaceEdge(pFaceAdd, pEdge)) {
            continue;
         }
         // calc edge length
         edgeLength = CalcDist(pEdge);
         // update distance from front 
         if (pFaceAdd->dist + edgeLength < pFaceNext->dist) {
            pFaceNext->dist     = pFaceAdd->dist + edgeLength;
            pFaceNext->prevFace = pFaceAdd;
         } 
      }
   }
   return;
}

/*************************************************************
* cgmWED_SYS::CalcBoundary ()
*
* IN:  pWED - winged-edge; selected faces (WED_STF_SELECTED)
*             specify the selected area
* OUT:      - filled states WED_ST?_SELECTED
*************************************************************/
void cgmWED_SYS::CalcBoundary (BOOL fUseSelEdges)
{
   int          edgeNmb, faceNmb, nodeNmb;
   cgmWED_EDGE *pEdge;
   cgmWED_FACE *pFace;
   cgmWED_NODE *pNode;

   for (edgeNmb = 0; edgeNmb < nEdge; edgeNmb++) {
      pEdge = &edgeList[edgeNmb];
      pEdge->state.Clear(CGM_WED_ST_BOUNDARY);
   }
   for (faceNmb = 0; faceNmb < nFace; faceNmb++) {
      pFace = &faceList[faceNmb];
      pFace->state.Clear(CGM_WED_ST_BOUNDARY);
   }
   for (nodeNmb = 0; nodeNmb < nNode; nodeNmb++) {
      pNode = &nodeList[nodeNmb];
      pNode->state.Clear(CGM_WED_ST_BOUNDARY);
   }

   for (edgeNmb = 0; edgeNmb < nEdge; edgeNmb++) {
      pEdge = &edgeList[edgeNmb];
      if (fUseSelEdges) {
         if (((pEdge->pFace1 && pEdge->pFace1->state.Is(CGM_WED_ST_SELECTED)) && (!pEdge->pFace2 || !pEdge->pFace2->state.Is(CGM_WED_ST_SELECTED))) ||
             ((pEdge->pFace2 && pEdge->pFace2->state.Is(CGM_WED_ST_SELECTED)) && (!pEdge->pFace1 || !pEdge->pFace1->state.Is(CGM_WED_ST_SELECTED)))) {
            pEdge->state.Set(CGM_WED_ST_BOUNDARY);
            pEdge->pNode1->state.Set(CGM_WED_ST_BOUNDARY);
            pEdge->pNode2->state.Set(CGM_WED_ST_BOUNDARY);
         }
      } else {
         if (pEdge->pFace1 && !pEdge->pFace2) {
            pEdge->state.Set(CGM_WED_ST_BOUNDARY);
            pEdge->pNode1->state.Set(CGM_WED_ST_BOUNDARY);
            pEdge->pNode2->state.Set(CGM_WED_ST_BOUNDARY);
         }
      }
   }
   for (faceNmb = 0; faceNmb < nFace; faceNmb++) {
      pFace = &faceList[faceNmb];
      for (edgeNmb = 0; edgeNmb < pFace->nEdge; edgeNmb++) {
         pEdge = pFace->edgeList[edgeNmb];
         if (pEdge->state.Is(CGM_WED_ST_BOUNDARY)) {
            pFace->state.Set(CGM_WED_ST_BOUNDARY);
         }
      }
   }

   return;
}

/*************************************************************
* cgmWED_SYS::DepthSearch()
*    Depth First Search in graph (see Lypski p. 89)
* 
* IN  : winged-edge structure, current node, current connectivity 
*       component number
*************************************************************/
void cgmWED_SYS::DepthSearch (cgmWED_NODE *pNode, int curCompNmb, cgmQUERY *pQuery)
{
   // store connectivity component number
   pNode->compNmb = curCompNmb;
   // for all incident edges
   for (int i = 0; i < pNode->nEdge; i ++) {
      cgmWED_EDGE * pEdge = pNode->edgeList[i];
      // choose incident node
      cgmWED_NODE * pNodeNew = pNode->IncidentNode(pEdge);
      // skip processed nodes
      if (pNodeNew->processedState == processedState) {
         continue;
      }
      // call user edge callback
      if (!pQuery->ProcessEdge(pNode, pEdge)) {
         continue;
      }
      pNodeNew->processedState = processedState;
      if (!pQuery->ProcessNode(pEdge, pNodeNew)) {
         // stop search 
         continue;
      }
      // visit new node
      DepthSearch(pNodeNew, curCompNmb, pQuery);
   }
}

/*************************************************************
* cgmWED_SYS::FaceDepthSearch ()
*    Depth First Search in graph (see Lypski p. 89)
* 
* IN: component number
*************************************************************/
void cgmWED_SYS::FaceDepthSearch (cgmWED_FACE *pFace, int curCompNmb, cgmQUERY *pQuery)
{
   // store connectivity component number
   pFace->compNmb = curCompNmb;

   // for all incident faces
   for (int i = 0; i < pFace->nEdge; i++) {
      cgmWED_EDGE * pEdge = pFace->edgeList[i];
      // choose incident node
      cgmWED_FACE * pFaceNew = pFace->IncidentFace(pEdge);
      // skip invalid node
      if (pFaceNew == NULL) {
         continue;
      }
      // skip processed nodes
      if (pFaceNew->processedState == processedState) {
         continue;
      }
      // call user edge callback
      if (!pQuery->ProcessEdge((cgmWED_FACE*)NULL, pEdge)) {
         continue;   
      }
      pFaceNew->processedState = processedState;
      // visit new node
      FaceDepthSearch(pFaceNew, curCompNmb, pQuery);
   }
   return;
}

/***************************************************************
* cgmQUERY_BOUNDARY::ProcessEdge()
*
***************************************************************/
BOOL cgmQUERY_BOUNDARY::ProcessEdge (cgmWED_NODE *pSrcNode, cgmWED_EDGE *pEdge)
{
   cgmWED_NODE *pDstNode = pSrcNode->IncidentNode(pEdge);

   if (pEdge->state.Is(CGM_WED_ST_BOUNDARY)) {
      return TRUE;
   }

   if (!pSrcNode->state.Is(CGM_WED_ST_BOUNDARY) &&
       !pDstNode->state.Is(CGM_WED_ST_BOUNDARY)) {
      return TRUE;
   }
   return FALSE;
}

//
// End-of-file CGM_WED_ALGO.CPP
//
